// 合并两个有序数组(在两个数组上归并)
function merge_two_sortedArr (arr1, arr2) {
  const l1 = arr1.length
  const l2 = arr2.length
  let p = 0
  let q = 0
  let res = []
  while (p < l1 || q < l2) {
    if (p === l1) {
      res.push(arr2[q++])
    } else if (q === l2) {
      res.push(arr1[p++])
    } else if (arr1[p] < arr2[q]) {
      res.push(arr1[p++])
    } else {
      res.push(arr2[q++])
    }
  }
  return res
}
let arr1 = [1, 4, 6]
let arr2 = [3, 12, 88]
console.log(merge_two_sortedArr(arr1, arr2))
// 在原数组上进行归并
function merge_in_place (arr, l, mid, r) {
  let keep = []
  for (let i = l; i <= r; i++) {
    keep[i] = arr[i]
  }
  let p = l
  let q = mid + 1
  for (let i = l; p <= mid || q <= r; i++) {
    if (p === mid + 1) {
      arr[i] = keep[q++]
    } else if (q === r + 1) {
      arr[i] = keep[p++]
    } else if (keep[p] < keep[q]) {
      arr[i] = keep[p++]
    } else {
      arr[i] = keep[q++]
    }
  }
  return keep
}
let arr = [1, 4, 5, 2, 3, 6, 7]
merge_in_place(arr, 0, 2, arr.length - 1)
console.log(arr)
// 归并排序
function merge (arr, l, mid, r) {
  const keep = []
  for (let i = l; i <= r; i++) {
    keep[i] = arr[i]
  }

  for (let p = l, q = mid + 1, k = l; p <= mid || q <= r;) {
    if (p === mid + 1) arr[k++] = keep[q++]
    else if (q === r + 1) arr[k++] = keep[p++]
    else if (keep[p] > keep[q]) arr[k++] = keep[q++]
    else arr[k++] = keep[p++]
  }
}

function mSort (arr, l, r) {
  if (l >= r) return
  // 分半
  const mid = l + Math.floor((r - l) / 2)
  // 归并排序左侧
  mSort(arr, l, mid)
  // 归并排序右侧
  mSort(arr, mid + 1, r)
  // 走到这里， l~mid 部分已排序，mid+1~r 部分已排序
  // 直接原地归并操作就可以实现数组排序
  merge(arr, l, mid, r)
}

function MergeSort (arr) {
  mSort(arr, 0, arr.length - 1)
}

const nums = [12, 1, 7, 4, 5, 2, 10, 6, 3, 11, 9, 8, 13]
MergeSort(nums)
console.log(nums);


